# there is a fast sampling algorithm used in the c++ program
# this R script is used to show the correctness of that fast sampling algorithm

fit <- c(10,100,890);
gt <- c("low","mid","high");

samp <- function(allSmp,smpWeights,n) {
	res <- c();
	total <- sum(smpWeights);
	i=1; #i=0 is index from 0
	v = allSmp[1];
	w = smpWeights[1];
	while(n>0) {
		x = total * (1 - (runif(1,0,1) ** (1 / n)));
		total = total - x;
		getThis <- c();
		while(x>w) {
			x = x - w;
			i = i + 1;
			w <- smpWeights[i];
		}
		w = w - x;
		res <- c(res,allSmp[i]);
		n = n - 1;
	}
	return(res);
}


ttt <- lapply(c(1:100),function(x){
	got <- samp(gt,fit,1000);
	tmp <- sapply(split(got,got),length);
	return(tmp)
})

rowMeans(data.frame(ttt))